package uestc.lj.midPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/12/2
 */
public class Code09_CompriseWays {
	/**
	 * 在不超过背包容量的前提下，最多有多少种
	 *
	 * @param arr 数组
	 * @param w   容量
	 * @return
	 */
	public static int ways(int[] arr, int w) {
		if (arr == null || arr.length == 0 || w < 0) {
			return 0;
		}
		int[][] dp = new int[arr.length][w + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[i][0] = 1;
		}
		for (int j = 1; j <= w; j++) {
			dp[0][j] = j >= arr[0] ? 2 : 1;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j <= w; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - arr[i] >= 0) {
					dp[i][j] += dp[i - 1][j - arr[i]];
				}
			}
		}
		return dp[arr.length - 1][w];
	}
}
